package com.yanceysong.codetop.s1_s10;

import com.yanceysong.common.ListNode;

/**
 * @ClassName S4_Hard_K个一组翻转链表
 * @Description
 * @date 2025/8/17 21:51
 * @Author yanceysong
 * @Version 1.0
 */
public class S5_Hard_25_K_个一组翻转链表 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/">...</a>
     * <p>
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     * <p>
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * <p>
     * 你不能只是单纯地改变节点内部的值，而是需要实际进行节点交换。
     * <p>
     * 示例1：k = 2
     * 原始链表: 1 -> 2 -> 3 -> 4 -> 5
     * 翻转后:   2 -> 1 -> 4 -> 3 -> 5
     * 图解:
     * 1 -> 2 -> 3 -> 4 -> 5
     * |↓   ↓|  |↓    ↓|   -
     * 2 -> 1 -> 4 -> 3 -> 5
     * <p>
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     * <p>
     * 示例2：k = 3
     * 原始链表: 1 -> 2 -> 3 -> 4 -> 5
     * 翻转后:   3 -> 2 -> 1 -> 4 -> 5
     * 图解:
     * 1 -> 2 -> 3 -> 4 -> 5
     * |↓   ↓    ↓|   -    -
     * 3 -> 2 -> 1 -> 4 -> 5
     * 输入：head = [1,2,3,4,5], k = 3
     * 输出：[3,2,1,4,5]
     * <p>
     * 提示：
     * 链表中的节点数目为 n
     * 1 <= k <= n <= 5000
     * 0 <= Node.val <= 1000
     * <p>
     * <p>
     * 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
     * 解题：
     * {@link S5_Hard_25_K_个一组翻转链表#reverseKGroupEfficient(com.yanceysong.common.ListNode, int)}
     * <p>
     * ==================== K个一组翻转链表算法图解 ====================
     * <p>
     * 算法思路：递归 + 头插法翻转
     * 1. 使用头插法翻转前k个节点
     * 2. 如果不足k个节点，则再次翻转回原状态
     * 3. 递归处理剩余部分
     * 4. 连接翻转后的部分和递归结果
     * <p>
     * 执行示例：[1,2,3,4,5], k=3
     * <p>
     * 初始状态：
     * head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     * <p>
     * 第1步：翻转前3个节点 (使用头插法)
     * 初始: head=1, currentTail=1, currentNode=2
     * 1 -> 2 -> 3 -> 4 -> 5
     * <p>
     * 头插法过程：
     * 步骤1: 将2插入到head前面
     * currentTail.next = currentNode.next  // 1.next = 3
     * currentNode.next = head              // 2.next = 1
     * head = currentNode                   // head = 2
     * 结果: 2 -> 1 -> 3 -> 4 -> 5
     * <p>
     * 步骤2: 将3插入到head前面
     * currentTail.next = currentNode.next  // 1.next = 4
     * currentNode.next = head              // 3.next = 2
     * head = currentNode                   // head = 3
     * 结果: 3 -> 2 -> 1 -> 4 -> 5
     * <p>
     * 第2步：检查是否翻转了k个节点
     * reversedCount = 3 == k，翻转成功
     * <p>
     * 第3步：递归处理剩余部分 [4,5]
     * 剩余节点不足k=3个，保持原状: 4 -> 5
     * <p>
     * 第4步：连接结果
     * currentTail.next = 递归结果
     * 最终: 3 -> 2 -> 1 -> 4 -> 5
     * <p>
     * 关键变量说明：
     * - head: 当前组的新头节点（翻转后）
     * - currentTail: 当前组翻转后的尾节点（原来的头节点）
     * - currentNode: 当前要插入的节点
     * - reversedCount: 已翻转的节点数量
     * - nextGroupHead: 下一组的头节点
     * <p>
     * 时间复杂度：O(n)，每个节点最多被访问2次（翻转+可能的回转）
     * 空间复杂度：O(n/k)，递归调用栈的深度
     * <p>
     * ================================================================
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 边界检查：空链表直接返回
        if (head == null) return null;

        // 初始化变量：使用头插法翻转前k个节点
        ListNode currentTail = head;           // 当前组翻转后的尾节点（原头节点）
        ListNode currentNode = head.next;      // 当前要处理的节点
        int reversedCount = 0;                 // 已翻转的节点计数

        // 使用头插法翻转前k个节点
        while (++reversedCount < k && currentNode != null) {
            // 头插法的三步操作：
            // 1. 断开当前节点，让尾节点指向下一个节点
            currentTail.next = currentNode.next;

            // 2. 将当前节点插入到头部
            currentNode.next = head;
            head = currentNode;

            // 3. 更新当前节点为尾节点的下一个节点
            currentNode = currentTail.next;
        }

        // 检查是否成功翻转了k个节点
        if (reversedCount < k) {
            // 不足k个节点，需要翻转回原状态
            // 递归调用自己，将已翻转的部分再翻转回去
            return reverseKGroup(head, reversedCount);
        }

        // 成功翻转k个节点，递归处理剩余部分
        ListNode nextGroupHead = currentNode;  // 下一组的头节点
        currentTail.next = reverseKGroup(nextGroupHead, k);

        // 返回当前组翻转后的头节点
        return head;
    }

    /**
     * ==================== O(1)空间复杂度解法 ====================
     * <p>
     * 算法思路：迭代 + 虚拟头节点 + 分组翻转
     * 1. 使用虚拟头节点简化边界处理
     * 2. 迭代找到每组的起始和结束位置
     * 3. 翻转每组内的节点（使用标准链表翻转）
     * 4. 连接翻转后的组到主链表
     * 5. 重复直到处理完所有组
     * <p>
     * 执行示例：[1,2,3,4,5], k=3
     * <p>
     * 初始状态：
     * dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     * <p>
     * 第1轮：处理第一组[1,2,3]
     * 1. 找到组边界：groupStart=1, groupEnd=3
     * 2. 翻转组内节点：1->2->3 变成 3->2->1
     * 3. 连接到主链表：dummy -> 3 -> 2 -> 1 -> 4 -> 5
     * <p>
     * 第2轮：处理第二组[4,5]
     * 1. 找到组边界：groupStart=4, groupEnd=5
     * 2. 节点数不足k=3，保持原状
     * 3. 最终结果：dummy -> 3 -> 2 -> 1 -> 4 -> 5
     * <p>
     * 关键变量说明：
     * - dummyHead: 虚拟头节点，简化边界处理
     * - prevGroupTail: 上一组的尾节点
     * - groupStart: 当前组的第一个节点
     * - groupEnd: 当前组的最后一个节点
     * - nextGroupHead: 下一组的第一个节点
     * <p>
     * 时间复杂度：O(n)，每个节点被访问常数次
     * 空间复杂度：O(1)，只使用常数个额外变量
     * <p>
     * ================================================================
     */
    public ListNode reverseKGroupEfficient(ListNode head, int k) {
        if (head == null || k == 1) return head;

        // 创建虚拟头节点，简化边界处理
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // 初始化指针
        ListNode prevGroupTail = dummyHead;  // 上一组的尾节点

        while (true) {
            // 步骤1：检查剩余节点是否足够k个
            ListNode groupStart = prevGroupTail.next;  // 当前组的第一个节点
            if (groupStart == null) break;             // 没有更多节点

            // 找到当前组的最后一个节点
            ListNode groupEnd = groupStart;
            for (int i = 1; i < k && groupEnd != null; i++) {
                groupEnd = groupEnd.next;
            }

            // 如果不足k个节点，结束处理
            if (groupEnd == null) break;

            // 步骤2：保存下一组的头节点
            ListNode nextGroupHead = groupEnd.next;

            // 步骤3：翻转当前组内的节点
            // 断开当前组与后续节点的连接
            groupEnd.next = null;

            // 翻转当前组：groupStart -> ... -> groupEnd 变成 groupEnd -> ... -> groupStart
            ListNode reversedGroupHead = reverseLinkedList(groupStart);

            // 步骤4：连接翻转后的组到主链表
            prevGroupTail.next = reversedGroupHead;  // 连接上一组的尾部到翻转后的头部
            // groupStart 这个时候它是当前组的尾节点
            groupStart.next = nextGroupHead;         // 连接翻转后的尾部到下一组的头部

            // 步骤5：更新指针，准备处理下一组
            prevGroupTail = groupStart;  // 当前组翻转后，原来的头节点变成了尾节点
        }

        return dummyHead.next;
    }

    /**
     * 辅助方法：翻转链表（标准算法）
     * 输入：1 -> 2 -> 3 -> null
     * 输出：3 -> 2 -> 1 -> null
     */
    private ListNode reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;  // 保存下一个节点
            current.next = prev;               // 反转指针
            prev = current;                    // 移动prev指针
            current = nextNode;                // 移动current指针
        }

        return prev;  // prev是新的头节点
    }

    public static void main(String[] args) {
        S5_Hard_25_K_个一组翻转链表 solution = new S5_Hard_25_K_个一组翻转链表();

        System.out.println("=== K个一组翻转链表测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同K值测试
        System.out.println("\n--- 测试3: 不同K值测试 ---");
        testDifferentKValues(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 测试6: O(1)空间复杂度解法测试
        System.out.println("\n--- 测试6: O(1)空间复杂度解法测试 ---");
        testIterativeMethod(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 创建链表的辅助方法
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }

    /**
     * 将链表转换为数组的辅助方法
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 先计算链表长度
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // 转换为数组
        int[] result = new int[length];
        current = head;
        for (int i = 0; i < length; i++) {
            result[i] = current.val;
            current = current.next;
        }

        return result;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        if (arr.length == 0) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S5_Hard_25_K_个一组翻转链表 solution) {
        // 示例1: [1,2,3,4,5], k=2 -> [2,1,4,3,5]
        int[] input1 = {1, 2, 3, 4, 5};
        int k1 = 2;
        int[] expected1 = {2, 1, 4, 3, 5};

        ListNode head1 = createList(input1);
        ListNode result1 = solution.reverseKGroup(head1, k1);
        int[] actual1 = listToArray(result1);

        System.out.print("输入: ");
        printArray(input1);
        System.out.print(", k=" + k1 + " -> 输出: ");
        printArray(actual1);
        System.out.print(" (期望: ");
        printArray(expected1);
        System.out.println(")");

        assert java.util.Arrays.equals(actual1, expected1) : "示例1测试失败";

        // 示例2: [1,2,3,4,5], k=3 -> [3,2,1,4,5]
        int[] input2 = {1, 2, 3, 4, 5};
        int k2 = 3;
        int[] expected2 = {3, 2, 1, 4, 5};

        ListNode head2 = createList(input2);
        ListNode result2 = solution.reverseKGroup(head2, k2);
        int[] actual2 = listToArray(result2);

        System.out.print("输入: ");
        printArray(input2);
        System.out.print(", k=" + k2 + " -> 输出: ");
        printArray(actual2);
        System.out.print(" (期望: ");
        printArray(expected2);
        System.out.println(")");

        assert java.util.Arrays.equals(actual2, expected2) : "示例2测试失败";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S5_Hard_25_K_个一组翻转链表 solution) {
        // 测试1: 空链表
        ListNode result1 = solution.reverseKGroup(null, 2);
        System.out.println("空链表: null, k=2 -> " + (result1 == null ? "null" : "非null") + " (期望: null)");
        assert result1 == null : "空链表测试失败";

        // 测试2: 单节点链表, k=1
        int[] input2 = {1};
        int[] expected2 = {1};
        ListNode head2 = createList(input2);
        ListNode result2 = solution.reverseKGroup(head2, 1);
        int[] actual2 = listToArray(result2);

        System.out.print("单节点k=1: ");
        printArray(input2);
        System.out.print(", k=1 -> ");
        printArray(actual2);
        System.out.print(" (期望: ");
        printArray(expected2);
        System.out.println(")");

        assert java.util.Arrays.equals(actual2, expected2) : "单节点k=1测试失败";

        // 测试3: 单节点链表, k=2 (不足k个)
        int[] input3 = {1};
        int[] expected3 = {1};
        ListNode head3 = createList(input3);
        ListNode result3 = solution.reverseKGroup(head3, 2);
        int[] actual3 = listToArray(result3);

        System.out.print("单节点k=2: ");
        printArray(input3);
        System.out.print(", k=2 -> ");
        printArray(actual3);
        System.out.print(" (期望: ");
        printArray(expected3);
        System.out.println(")");

        assert java.util.Arrays.equals(actual3, expected3) : "单节点k=2测试失败";

        // 测试4: 链表长度等于k
        int[] input4 = {1, 2, 3};
        int[] expected4 = {3, 2, 1};
        ListNode head4 = createList(input4);
        ListNode result4 = solution.reverseKGroup(head4, 3);
        int[] actual4 = listToArray(result4);

        System.out.print("长度等于k: ");
        printArray(input4);
        System.out.print(", k=3 -> ");
        printArray(actual4);
        System.out.print(" (期望: ");
        printArray(expected4);
        System.out.println(")");

        assert java.util.Arrays.equals(actual4, expected4) : "长度等于k测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同K值
     */
    private static void testDifferentKValues(S5_Hard_25_K_个一组翻转链表 solution) {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8};

        // k=1: 不翻转
        int[] expected1 = {1, 2, 3, 4, 5, 6, 7, 8};
        testKValue(solution, input, 1, expected1, "k=1不翻转");

        // k=2: 两两翻转
        int[] expected2 = {2, 1, 4, 3, 6, 5, 8, 7};
        testKValue(solution, input, 2, expected2, "k=2两两翻转");

        // k=4: 四个一组翻转
        int[] expected4 = {4, 3, 2, 1, 8, 7, 6, 5};
        testKValue(solution, input, 4, expected4, "k=4四个一组");

        // k=8: 整个链表翻转
        int[] expected8 = {8, 7, 6, 5, 4, 3, 2, 1};
        testKValue(solution, input, 8, expected8, "k=8整个翻转");

        // k=5: 不能整除的情况
        int[] expected5 = {5, 4, 3, 2, 1, 6, 7, 8};
        testKValue(solution, input, 5, expected5, "k=5不能整除");

        System.out.println("✓ 不同K值测试通过");
    }

    /**
     * 辅助方法：测试特定K值
     */
    private static void testKValue(S5_Hard_25_K_个一组翻转链表 solution, int[] input, int k, int[] expected, String description) {
        ListNode head = createList(input);
        ListNode result = solution.reverseKGroup(head, k);
        int[] actual = listToArray(result);

        System.out.print(description + " - ");
        printArray(input);
        System.out.print(", k=" + k + " -> ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S5_Hard_25_K_个一组翻转链表 solution) {
        // 测试1: 包含负数
        int[] input1 = {-1, -2, 3, 4};
        int[] expected1 = {-2, -1, 4, 3};
        testKValue(solution, input1, 2, expected1, "包含负数");

        // 测试2: 相同元素
        int[] input2 = {1, 1, 1, 1, 1, 1};
        int[] expected2 = {1, 1, 1, 1, 1, 1};
        testKValue(solution, input2, 3, expected2, "相同元素");

        // 测试3: 大数值
        int[] input3 = {100, 200, 300, 400, 500};
        int[] expected3 = {200, 100, 400, 300, 500};
        testKValue(solution, input3, 2, expected3, "大数值");

        // 测试4: 两个节点
        int[] input4 = {1, 2};
        int[] expected4 = {2, 1};
        testKValue(solution, input4, 2, expected4, "两个节点");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S5_Hard_25_K_个一组翻转链表 solution) {
        // 测试1: 中等长度链表
        System.out.println("性能测试1: 100个节点");
        testPerformanceCase(solution, 100, 5);

        // 测试2: 较长链表
        System.out.println("性能测试2: 500个节点");
        testPerformanceCase(solution, 500, 10);

        // 测试3: 长链表
        System.out.println("性能测试3: 1000个节点");
        testPerformanceCase(solution, 1000, 20);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S5_Hard_25_K_个一组翻转链表 solution, int length, int k) {
        // 创建测试链表
        int[] input = new int[length];
        for (int i = 0; i < length; i++) {
            input[i] = i + 1;
        }

        ListNode head = createList(input);

        long startTime = System.currentTimeMillis();
        ListNode result = solution.reverseKGroup(head, k);
        long endTime = System.currentTimeMillis();

        // 验证结果不为空
        assert result != null : "性能测试：结果不应为空";

        int[] resultArray = listToArray(result);
        assert resultArray.length == length : "性能测试：结果长度应该等于输入长度";

        System.out.println("  链表长度: " + length + ", k=" + k +
                ", 结果长度: " + resultArray.length +
                ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度合理
        assert (endTime - startTime) < 1000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 测试O(1)空间复杂度的迭代解法
     */
    private static void testIterativeMethod(S5_Hard_25_K_个一组翻转链表 solution) {
        System.out.println("对比递归解法和迭代解法的结果一致性：");

        // 测试用例1: 基本示例
        int[] input1 = {1, 2, 3, 4, 5};
        int k1 = 2;
        compareResults(solution, input1, k1, "基本示例k=2");

        // 测试用例2: k=3的情况
        int[] input2 = {1, 2, 3, 4, 5};
        int k2 = 3;
        compareResults(solution, input2, k2, "基本示例k=3");

        // 测试用例3: 完全翻转
        int[] input3 = {1, 2, 3, 4};
        int k3 = 4;
        compareResults(solution, input3, k3, "完全翻转");

        // 测试用例4: 不足k个节点
        int[] input4 = {1, 2};
        int k4 = 3;
        compareResults(solution, input4, k4, "不足k个节点");

        // 测试用例5: 单节点
        int[] input5 = {1};
        int k5 = 1;
        compareResults(solution, input5, k5, "单节点");

        // 测试用例6: 空链表
        int[] input6 = {};
        int k6 = 2;
        compareResults(solution, input6, k6, "空链表");

        // 测试用例7: 复杂情况
        int[] input7 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int k7 = 3;
        compareResults(solution, input7, k7, "复杂情况");

        // 性能对比测试
        System.out.println("\n性能对比测试：");
        performanceComparison(solution);

        System.out.println("✓ O(1)空间复杂度解法测试通过");
    }

    /**
     * 比较递归解法和迭代解法的结果
     */
    private static void compareResults(S5_Hard_25_K_个一组翻转链表 solution, int[] input, int k, String description) {
        // 创建两个相同的链表
        ListNode head1 = createList(input);
        ListNode head2 = createList(input);

        // 分别用两种方法处理
        ListNode result1 = solution.reverseKGroup(head1, k);
        ListNode result2 = solution.reverseKGroupEfficient(head2, k);

        // 转换为数组比较
        int[] array1 = listToArray(result1);
        int[] array2 = listToArray(result2);

        System.out.print(description + " - 输入: ");
        printArray(input);
        System.out.print(", k=" + k);
        System.out.print(" -> 递归: ");
        printArray(array1);
        System.out.print(", 迭代: ");
        printArray(array2);

        // 验证结果一致
        boolean isEqual = java.util.Arrays.equals(array1, array2);
        System.out.println(isEqual ? " ✓" : " ✗");

        assert isEqual : description + "：递归和迭代结果不一致";
    }

    /**
     * 性能对比测试
     */
    private static void performanceComparison(S5_Hard_25_K_个一组翻转链表 solution) {
        int[] testSizes = {100, 500, 1000};
        int k = 5;

        for (int size : testSizes) {
            // 创建测试数据
            int[] input = new int[size];
            for (int i = 0; i < size; i++) {
                input[i] = i + 1;
            }

            // 测试递归方法
            ListNode head1 = createList(input);
            long start1 = System.currentTimeMillis();
            ListNode result1 = solution.reverseKGroup(head1, k);
            long end1 = System.currentTimeMillis();
            long time1 = end1 - start1;

            // 测试迭代方法
            ListNode head2 = createList(input);
            long start2 = System.currentTimeMillis();
            ListNode result2 = solution.reverseKGroupEfficient(head2, k);
            long end2 = System.currentTimeMillis();
            long time2 = end2 - start2;

            // 验证结果一致性
            int[] array1 = listToArray(result1);
            int[] array2 = listToArray(result2);
            assert java.util.Arrays.equals(array1, array2) : "性能测试：结果不一致";

            System.out.println("  规模" + size + " - 递归: " + time1 + "ms, 迭代: " + time2 + "ms");
        }
    }
}
